// https://leetcode.cn/problems/swap-nodes-in-pairs/description/

// 算法思路总结：
// 1. 递归实现两两交换链表中的节点
// 2. 基准情况：空链表或单节点链表直接返回
// 3. 递归交换后续节点对，保存结果
// 4. 交换当前节点对：第二个节点指向第一个，第一个指向后续结果
// 5. 返回新的头节点（原第二个节点）
// 6. 时间复杂度：O(n)，空间复杂度：O(n)（递归栈）

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

#include "LinkedListUtils.h"

class Solution 
{
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if (head == nullptr || head->next == nullptr)
            return head;

        auto tmp = swapPairs(head->next->next);
        auto ret = head->next;
        head->next->next = head;
        head->next = tmp;

        return ret;
    }
};

int main()
{
    vector<int> v1 = {1,2,3,4}, v2 = {}, v3 = {1};
    Solution sol;

    auto l1 = createLinkedList(v1);
    auto l2 = createLinkedList(v2);
    auto l3 = createLinkedList(v3);

    auto r1 = sol.swapPairs(l1);
    auto r2 = sol.swapPairs(l2);
    auto r3 = sol.swapPairs(l3);

    printLinkedList(r1);
    printLinkedList(r2);
    printLinkedList(r3);

    return 0;
}